Subsets

Time: O(Nx2^N); Space: O(1); medium

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example 1:

Input: nums = [1,2,3]

Output:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Example 2:

Input: [0]

Output:

[
  [],
  [0]
]

[5]:

class Solution1(object):
    """
    Time: O(N*2^N)
    Space: O(1)
    """
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = [[]]
        for i in range(len(nums)):
            size = len(result)
            for j in range(size):
                result.append(list(result[j]))
                result[-1].append(nums[i])

        return result

[13]:

s = Solution1()

nums = [1,2,3]
# print(s.subsets(nums))
assert s.subsets(nums)== [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

nums = [0]
assert s.subsets(nums)== [[],[0]] or [[0],[]]

[7]:

class Solution2(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        i, count = 0, 1 << len(nums)
        nums.sort()

        while i < count:
            cur = []
            for j in range(len(nums)):
                if i & 1 << j:
                    cur.append(nums[j])
            result.append(cur)
            i += 1

        return result

[14]:

s = Solution2()

nums = [1,2,3]
assert s.subsets(nums)== [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

nums = [0]
assert s.subsets(nums)== [[],[0]] or [[0],[]]

[9]:

class Solution3(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return self.subsetsRecu([], sorted(nums))

    def subsetsRecu(self, cur, nums):
        if not nums:
            return [cur]

        return self.subsetsRecu(cur, nums[1:]) + self.subsetsRecu(cur + [nums[0]], nums[1:])

[15]:

s = Solution3()

nums = [1,2,3]
# print(s.subsets(nums))
assert s.subsets(nums)== [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

nums = [0]
assert s.subsets(nums)== [[],[0]] or [[0],[]]